1. Field of the Invention
This invention relates generally to space management systems and, more particularly, to allocation of data space for large objects in relational database systems.
2. Description of the Related Art
Advances in computers and data storage devices have provided users with increasingly faster data access times and with the ability to manipulate information comprising increasingly large blocks of data values stored in data spaces of computer memory and data storage devices. Such advances place requirements on space management systems to manage increasingly larger data spaces and to allocate large amounts of available data space to data values more quickly.
One such space management technique is known as the binary buddy system. The buddy system generally is known to be a high performance space management system that can operate on a wide range of block sizes, allocating and freeing the blocks with great efficiency. The binary buddy system manages blocks, or memory segments, whose sizes correspond to powers of two. In the simplest description of the binary buddy system, the data space in which data values are contained includes a buddy space that has a size that is a power of two units large. For example, a buddy space might comprise four megabytes (written 4 MB) of storage locations, which actually corresponds to 4.times.1,024,000 bytes or 2.sup.12 bytes. The entire buddy space can be divided into two segments (known as buddy segments). In the example, the two segments would each be 2 MB in size. Each of these buddy segments can be further subdivided into two smaller buddy segments--and so on until a minimal buddy segment size is reached. That is, the buddy space can be comprised of multiple buddy segments, all of different sizes, all being powers of two. The minimal segment size that the system can allocate might be, for example, one kilobyte (1 KB) worth of data storage locations.
When a data value of a certain size is to be stored, a space allocator of the buddy system must allocate a buddy segment for the data value. In attempting to allocate a (power-of-2-size) buddy segment, the space allocator either finds a segment of the correct size, or finds a larger segment (starting with up to 4 MB in the example) and splits it down (subdivides) repeatedly to the desired size. Thus, buddy segments might be allocated in storage blocks of size 1 KB, 2 KB, 4 KB, 8 KB, . . . , 512 KB, 1 MB, and so on up to the buddy space size limit of the computer system in which the data base is installed. When freeing a buddy segment from storing a data value, the space allocator automatically joins that segment with its buddy (if the buddy is free). Similarly, that resulting larger segment is joined with its buddy if the buddy is free--and so on until the maximum size segment again is reached.
Typically, implementations of the buddy system space management technique have two main components: the space allocation information and the data space itself. The space allocation information includes the status of the buddy spaces with respect to subdivisions into buddy segments and the assignment of the buddy segments to data values. The computer system uses the allocation information to manage the allocation and freeing of storage locations for data values. When used to manage a computer memory space, the space allocation information is represented as a large main-memory data structure. When used to manage (large amounts of) disk storage, the space allocation information is represented as disk-resident data structures. Currently, the size of a buddy segment is bounded by the amount of allocation information that can be represented by a single disk page, i.e., if the largest buddy segment that a single disk page can represent is one megabyte in size, then no larger size buddy segment can easily be represented. Although one could represent larger sizes by simply stringing a set of maximum size segments together, this solution does not scale and actually introduces a significant amount of complexity in terms of tracking segment sizes and boundaries. For example, allocating space requires linear searches of the allocation information for free buddy segments, and therefore stringing buddy segments together causes the search to degrade in terms of speed as more spaces are added. For very large data values, the scheme is not useful, because too many disk access operations are required.
From the discussion above, it should be apparent that there is a need for a data space management system that permits reduced disk access operations in allocating, storing, and retrieving data values that are stored according to a buddy segment system of allocation. The present invention satisfies this need.